#include "classical-problems.h"

#include <time.h>
#include <set>
#include <iostream>

namespace pot {
template<typename T>
void copy(T s, T e, int *v) {
  for ( ; s != e; ++s) *v++ = *s;
}

class IntSetSTL {
public:
  IntSetSTL(int n_elements, int max_val) { }
  int size() const { return s_.size(); }
  void insert(int t) { s_.insert(t); }
  void report(int *v) const {
    pot::copy(s_.begin(), s_.end(), v);
  }
private:
  std::set<int> s_;
};

class IntSetArray {
public:
  IntSetArray(int n_elements, int max_val) : x_(NULL), n_(0) {
    x_ = new int[n_elements + 1];
    n_ = 0;
    x_[0] = max_val;
  }

  ~IntSetArray() { 
    if (NULL != x_) delete[] x_;
  }

  int size() const { return n_; }
  void insert(int t) {
    int i = 0;
    // use sentinel to save 1 comparison
    while (x_[i] < t) ++i;
    if (x_[i] == t) return;

    for (int j = n_; j >= i; --j) x_[j + 1] = x_[j];
    x_[i] = t;

    ++n_;
  }
  void report(int *v) const {
    pot::copy(x_, x_ + n_, v);
  }
private:
  int n_, *x_;
};

struct node {
  node() : val(0), next(NULL) { }
  node(int v, node *p) : val(v), next(p) { }
  int val;
  node *next;
};

class IntSetList {
public:
  IntSetList(int n_elements, int max_val) :
      head_(NULL), sentinel_(NULL), buffer_(NULL), free_nodes_(NULL), n_(0) {
    buffer_ = free_nodes_ = new node[n_elements + 1];
    head_ = sentinel_ = free_nodes_++;
    head_->val = max_val;
  }

  ~IntSetList() { if (NULL != buffer_) delete[] buffer_; }

  int size() const { return n_; }

  void insert(int t) {
    node **p = &head_;
    while ((*p)->val < t) p = &((*p)->next);

    if ((*p)->val == t) return;

    /*
     * *p may be head_, or (*(previous p))->next, 
     * thus **p refers to current node, 
     * (*p)->val refers to the value of current node
     */
    node *n = free_nodes_++;
    n->val = t;
    n->next = *p;
    *p = n;

    ++n_;
  }

  void report(int *v) const {
    for (node *p = head_; p != sentinel_; p = p->next)
      *v++ = p->val;
  }

private:
  node *free_nodes_, *buffer_;
  int n_;
  node *head_;
  node *sentinel_;
};

struct tnode {
  tnode(int val) : val(val), left(NULL), right(NULL) { }
  tnode() : val(0), left(NULL), right(NULL) { }

  int val;
  tnode *left, *right;
};
class IntSetBST {
public:
  IntSetBST(int n_elements, int max_val) :
      root_(NULL), buffer_(NULL), free_nodes_(NULL), n_(0) {
    buffer_ = free_nodes_ = new tnode[n_elements + 1];
    root_ = sentinel_ = free_nodes_++;
  }
  ~IntSetBST() { if (NULL != buffer_) delete[] buffer_; }

  int size() const { return n_; }

  void insert(int t) {
    sentinel_->val = t;
    tnode **p = &root_;

    /* use sentinel_ to terminate the loop
     */
    while ((*p)->val != t) {
      if ((*p)->val > t) {
        p = &((*p)->left);
      }
      else if ((*p)->val < t) {
        p = &((*p)->right);
      }
    }

    /*
     * *p is root_, or (*(previous parent))->left,
     * or (*(previous parent))->right
     * if it points to sentinel(NULL), a new node should be added for t,
     * and the node should have its left and right point to sentinel(NULL)
     */
    if (*p == sentinel_) {
      *p = free_nodes_++;
      (*p)->val = t;
      (*p)->left = (*p)->right = sentinel_;
      ++n_;
    }
    // otherwise, t exists in the tree
  }

  void report(int *v) const {
    this->traverse(root_, &v);
  }
private:
  void traverse(tnode *p, int **v) const {
    if (sentinel_ == p) return;
    this->traverse(p->left, v);
    *(*v)++ = p->val;
    this->traverse(p->right, v);
  }
private:
  tnode *root_, *sentinel_;
  tnode *free_nodes_, *buffer_;
  int n_;
};

class IntSetBitVec {
public:
  IntSetBitVec(int n_elements, int max_val) : vec_(NULL), n_(0), max_val_(0) { 
    int nints = (max_val + 31) / 32;
    vec_ = new int[nints];
    memset(vec_, 0, sizeof(int) * nints);
    max_val_ = max_val;
  }
  ~IntSetBitVec() { if (NULL != vec_) delete[] vec_; }

  int size() const { return n_; }

  void insert(int t) {
    if (test(t) != 0) return;
    this->set(t);
    ++n_;
  }

  void report(int *v) const {
    for (int i = 0; i < max_val_; ++i) {
      if (test(i) != 0) *v++ = i;
    }
  }
private:
  void set(int i) { vec_[this->idx(i)] |= this->bit(i); }
  void clr(int i) { vec_[this->idx(i)] &= ~this->bit(i); }
  int test(int i) const { return vec_[this->idx(i)] & this->bit(i); }

  static int bit(int i) { return (1 << (i & 0x1F)); }
  static int idx(int i) { return (i >> 5); }
private:
  int *vec_;
  int n_;
  int max_val_;
};

class IntSetBins {
public:
  IntSetBins(int n_elements, int max_val) : 
      n_(0), bins_(0), max_val_(0), buffer_(NULL), free_nodes_(NULL), bin_(NULL) {
    bin_ = new node*[n_elements];
    bins_ = n_elements;
    max_val_ = max_val;

    buffer_ = free_nodes_ = new node[n_elements + 1];
    sentinel_ = free_nodes_++;
    sentinel_->val = max_val;

    for (int i = 0; i < bins_; ++i) bin_[i] = sentinel_;
  }

  ~IntSetBins() {
    if (NULL != buffer_) delete[] buffer_;
    delete[] bin_;
  }

  int size() const { return n_; }

  void insert(int t) {
    int i = t / (1 + max_val_ / bins_);
    node **p = &bin_[i];
    while ((*p)->val < t) p = &((*p)->next);
    if ((*p)->val == t) return;

    node *n = free_nodes_++;
    n->val = t;
    n->next = *p;
    *p = n;
    ++n_;
  }

  void report(int *v) const {
    for (int i = 0; i < bins_; ++i) {
      for (node *p = bin_[i]; p != sentinel_; p = p->next) {
        *v++ = p->val;
      }
    }
  }

private:
  node **bin_;
  node *sentinel_;
  // alocate nodes in block, can save more than half the memory,
  // and runs faster
  node *buffer_, *free_nodes_;
  int n_, bins_, max_val_;
};

int bigrand() { return RAND_MAX * rand() + rand(); }

template<typename T>
void gensets(int m, int max_val, const char *msg = "") {
  clock_t t0 = clock();  
  T s(m, max_val);
  while (s.size() < m) s.insert(bigrand() % max_val);
  int *v = new int[m];
  s.report(v);
  clock_t t1 = clock();
  //for (int i = 0; i < m; ++i) std::cout << v[i] << ", ";
  for (int i = 1; i < m; ++i) {
    if (v[i - 1] >= v[i]) {
      printf("%s, error\n", msg);
      break;
    }
  }
  delete[] v;
  printf("%s, success, time = %f\n", msg, (t1 - t0) / 1000.0);
  /*printf("\n---------------------------------\n");*/
}

void RandomIntSetTest() {
  const int n = 100000000;
  const int k[] = { n / 10000, n / 5000, n / 2000, n / 1000, n / 100, n / 20, n / 10 };
  for (int i = 0; i < 7; ++i) {
    printf("\n-------------------------------------\n");
    printf("n = %d, k = %d\n", n, k[i]);

    if (i < 6) gensets<IntSetSTL>(k[i], n, "stl");
    if (i < 4) {
      gensets<IntSetArray>(k[i], n, "array");
      gensets<IntSetList>(k[i], n, "list");
    }
    gensets<IntSetBST>(k[i], n, "bst");
    gensets<IntSetBitVec>(k[i], n, "bit vector");
    gensets<IntSetBins>(k[i], n, "bins");
  }
}

} // pot

